<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: bin_heap&lt; T, Pred &gt; Class Template Reference</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li class="current"><a href="classes.html"><span>Classes</span></a></li>
    <li><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<div class="tabs">
  <ul>
    <li><a href="classes.html"><span>Alphabetical&nbsp;List</span></a></li>
    <li><a href="annotated.html"><span>Class&nbsp;List</span></a></li>
    <li><a href="hierarchy.html"><span>Class&nbsp;Hierarchy</span></a></li>
    <li><a href="functions.html"><span>Class&nbsp;Members</span></a></li>
  </ul>
</div>
<h1>bin_heap&lt; T, Pred &gt; Class Template Reference</h1><!-- doxytag: class="bin_heap" -->Binary heap.  
<a href="#_details">More...</a>
<p>

<p>
<a href="a00125.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd">bin_heap</a> (const Pred &amp;prd)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Creates empty binary heap.  <a href="#9de42b60fac4b0d38aa738522eb7c4cd"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#b911dd559d9d9fd665b9fdf2d8202bb8">bin_heap</a> (const Pred &amp;prd, const int est_size)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Creates empty binary heap.  <a href="#b911dd559d9d9fd665b9fdf2d8202bb8"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#19bd4241e097852ffda83b72557ffbdc">bin_heap</a> (const <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt; &amp;bh)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Copy constructor.  <a href="#19bd4241e097852ffda83b72557ffbdc"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt; &amp;&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#d31b6806316a272686015fcbf5f633cd">operator=</a> (const <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt; &amp;bh)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Assigns <code>bh</code> to this binary heap.  <a href="#d31b6806316a272686015fcbf5f633cd"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="5283db56783a84ee28dea9d393acf905"></a><!-- doxytag: member="bin_heap::~bin_heap" ref="5283db56783a84ee28dea9d393acf905" args="()" -->
&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#5283db56783a84ee28dea9d393acf905">~bin_heap</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Destructor. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#6d658d61533e66cf83dce2f8e35bed17">push</a> (const T &amp;ins)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Inserts <code>ins</code> in heap.  <a href="#6d658d61533e66cf83dce2f8e35bed17"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="b463bc655b2f46cd5ff021cab28b1210"></a><!-- doxytag: member="bin_heap::pop" ref="b463bc655b2f46cd5ff021cab28b1210" args="()" -->
void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#b463bc655b2f46cd5ff021cab28b1210">pop</a> ()</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Removes the element on top of the heap. <br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">const T &amp;&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#09924a9669f054bc6fdcf2dc5637f7f3">top</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns a reference to the element at the top of the heap.  <a href="#09924a9669f054bc6fdcf2dc5637f7f3"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#b1353fe40c5cfc1205314a4db6334f1b">changeKey</a> (const T &amp;cha)</td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Reconstructs heap condition after changing key value of <code>cha</code> externally.  <a href="#b1353fe40c5cfc1205314a4db6334f1b"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="a00006.html#6c6f5bf251a2a85ebdd1a1730eb7934d">is_empty</a> () const </td></tr>

<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Checks if heap is empty.  <a href="#6c6f5bf251a2a85ebdd1a1730eb7934d"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
<h3>template&lt;class T, class Pred&gt;<br>
 class bin_heap&lt; T, Pred &gt;</h3>

Binary heap. 
<p>
<dl class="author" compact><dt><b>Author:</b></dt><dd>Christian Bachmaier <a href="mailto:chris@infosun.fmi.uni-passau.de">chris@infosun.fmi.uni-passau.de</a> </dd></dl>
<hr><h2>Constructor &amp; Destructor Documentation</h2>
<a class="anchor" name="9de42b60fac4b0d38aa738522eb7c4cd"></a><!-- doxytag: member="bin_heap::bin_heap" ref="9de42b60fac4b0d38aa738522eb7c4cd" args="(const Pred &amp;prd)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::<a class="el" href="a00006.html">bin_heap</a>           </td>
          <td>(</td>
          <td class="paramtype">const Pred &amp;&nbsp;</td>
          <td class="paramname"> <em>prd</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Creates empty binary heap. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>prd</em>&nbsp;</td><td>binary predicate to compare two <code>T</code>s </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="b911dd559d9d9fd665b9fdf2d8202bb8"></a><!-- doxytag: member="bin_heap::bin_heap" ref="b911dd559d9d9fd665b9fdf2d8202bb8" args="(const Pred &amp;prd, const int est_size)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::<a class="el" href="a00006.html">bin_heap</a>           </td>
          <td>(</td>
          <td class="paramtype">const Pred &amp;&nbsp;</td>
          <td class="paramname"> <em>prd</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const int&nbsp;</td>
          <td class="paramname"> <em>est_size</em></td><td>&nbsp;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td><td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Creates empty binary heap. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>prd</em>&nbsp;</td><td>binary predicate to compare two <code>Ts</code> </td></tr>
    <tr><td valign="top"></td><td valign="top"><em>est_size</em>&nbsp;</td><td>estimated maximal size of heap </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="19bd4241e097852ffda83b72557ffbdc"></a><!-- doxytag: member="bin_heap::bin_heap" ref="19bd4241e097852ffda83b72557ffbdc" args="(const bin_heap&lt; T, Pred &gt; &amp;bh)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::<a class="el" href="a00006.html">bin_heap</a>           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt; &amp;&nbsp;</td>
          <td class="paramname"> <em>bh</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Copy constructor. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>bh</em>&nbsp;</td><td>binary heap to copy </td></tr>
  </table>
</dl>

</div>
</div><p>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="d31b6806316a272686015fcbf5f633cd"></a><!-- doxytag: member="bin_heap::operator=" ref="d31b6806316a272686015fcbf5f633cd" args="(const bin_heap&lt; T, Pred &gt; &amp;bh)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname"><a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt; &amp; <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::operator=           </td>
          <td>(</td>
          <td class="paramtype">const <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt; &amp;&nbsp;</td>
          <td class="paramname"> <em>bh</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Assigns <code>bh</code> to this binary heap. 
<p>
All elements in this heap will be deleted. The predicate of this heap must be physically the same as the one of <code>bh</code>.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>bh</em>&nbsp;</td><td>binary heap</td></tr>
  </table>
</dl>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>this heap </dd></dl>

</div>
</div><p>
<a class="anchor" name="6d658d61533e66cf83dce2f8e35bed17"></a><!-- doxytag: member="bin_heap::push" ref="6d658d61533e66cf83dce2f8e35bed17" args="(const T &amp;ins)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::push           </td>
          <td>(</td>
          <td class="paramtype">const T &amp;&nbsp;</td>
          <td class="paramname"> <em>ins</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Inserts <code>ins</code> in heap. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>ins</em>&nbsp;</td><td>data element to be inserted </td></tr>
  </table>
</dl>

</div>
</div><p>
<a class="anchor" name="09924a9669f054bc6fdcf2dc5637f7f3"></a><!-- doxytag: member="bin_heap::top" ref="09924a9669f054bc6fdcf2dc5637f7f3" args="() const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">const T &amp; <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::top           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Returns a reference to the element at the top of the heap. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>top element of the heap </dd></dl>

</div>
</div><p>
<a class="anchor" name="b1353fe40c5cfc1205314a4db6334f1b"></a><!-- doxytag: member="bin_heap::changeKey" ref="b1353fe40c5cfc1205314a4db6334f1b" args="(const T &amp;cha)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::changeKey           </td>
          <td>(</td>
          <td class="paramtype">const T &amp;&nbsp;</td>
          <td class="paramname"> <em>cha</em>          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"><code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Reconstructs heap condition after changing key value of <code>cha</code> externally. 
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign="top"></td><td valign="top"><em>cha</em>&nbsp;</td><td>element with changed key value</td></tr>
  </table>
</dl>
<dl class="note" compact><dt><b>Note:</b></dt><dd><code>changeKey</code> doesn't operate if <code>cha</code> is a primitive data structure, because it represents its key value itself, or if one object is stored more than once in the data structure.</dd></dl>
<dl class="see" compact><dt><b>See also:</b></dt><dd><a class="el" href="a00009.html" title="Dijkstra&#39;s Algorithm for computing single source shortest path.">dijkstra</a> </dd></dl>

</div>
</div><p>
<a class="anchor" name="6c6f5bf251a2a85ebdd1a1730eb7934d"></a><!-- doxytag: member="bin_heap::is_empty" ref="6c6f5bf251a2a85ebdd1a1730eb7934d" args="() const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;class T, class Pred&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">bool <a class="el" href="a00006.html">bin_heap</a>&lt; T, Pred &gt;::is_empty           </td>
          <td>(</td>
          <td class="paramname">          </td>
          <td>&nbsp;)&nbsp;</td>
          <td width="100%"> const<code> [inline]</code></td>
        </tr>
      </table>
</div>
<div class="memdoc">

<p>
Checks if heap is empty. 
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd><code>true</code> iff empty </dd></dl>

</div>
</div><p>
    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>
